class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());

        vector<vector<int>> ans;

        int sz = nums.size();

        int i = 0;  // 固定一个数
        while(i < sz)
        {   
            if(nums[i] > 0) break;  // 优化，>0 后面两个数之和不可能等于负数 

            int left = i + 1, right = sz - 1, target = -nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];

                if(sum > target) --right;
                else if(sum < target) ++left;
                else 
                {
                    ans.push_back({nums[i], nums[left++], nums[right--]});
                    
                    // 去重 left and right
                    while(left < right && nums[left] == nums[left - 1]) ++left;
                    while(left < right && nums[right] == nums[right + 1]) --right; 
                }
            }

            ++i;
            while(i < sz && nums[i] == nums[i - 1]) ++i;  // 去重 i
        }

        return ans;
    }
};